// 1.大数相加
const bigAdd = (a, b) => {
    let maxLen = Math.max(a.length, b.length);
    a = a.padStart(maxLen, 0);
    b = b.padStart(maxLen, 0);

    let curSum = 0;
    let carry = 0;
    let sum = "";
    for(let i = maxLen-1; i >= 0; i--) {
        curSum = parseInt(a[i]) + parseInt(b[i]) + carry;
        carry = Math.floor(curSum / 10);
        sum = curSum % 10 + sum;
    }
    if( carry === 1 )
        sum = '1' + sum;
    return sum;
}

let a = "9007199254740991";      //16位数，JS中number类型的最大安全范围，超出可能损失精度
let b = "1234567899999999999";   //20位数


console.log(bigAdd(a, b)); 
console.log(9007199254740991 + 1234567899999999999);



// 2.带并发限制的fetch
function sendRequest(urls, max, callback){
    let pending_count = 0;
    let idx = 0;
    while(pending_count < max)
        _fetch(urls[idx++]);

    async function _fetch(url){
        if(!url) return;
        pending_count++;
        console.log(url + 'start' + '并发数量:' + pending_count);
        await fetch(url);
        pending_count--;
        console.log(url + 'done' + '并发数量:' + pending_count);
        _fetch(urls[idx++]);
        pending_count || callback && callback();
    }
}

let urls = Array.from({length: 10},(_,index)=>index);

let fetch = function(idx){
    return new Promise(resolve => {
        let timeout = parseInt(Math.random() * 1e4);
        setTimeout(() => {
            resolve(idx)
        },timeout);
    })
}

let max = 4;
let callback = () => {
    console.log('run callback');
}

sendRequest(urls, max, callback);

// 二分查找
function binary_search(arr, low, high, key) {
    if (low > high)
        return -1;
    var mid = parseInt((low + high)/2);
    if(arr[mid] === key)
        return mid;
    else if(arr[mid] > key){
        high = mid - 1;
        return binary_search(arr,low,high,key);
    }else if (arr[mid] < key){
        low = mid + 1;
        return binary_search(arr,low,high,key);
    }
};

const sortedArr = [1,2,3,4,5,6,7,8];
const key = 7;
console.log(binary_search(sortedArr, 0, sortedArr.length, key));

// 发布订阅模式
function Subject() {
    this.observers = [];
}

Subject.prototype = {
    subscribe: function(observer){
        this.observers.push(observer);
    },

    unsubscribe: function(observerToRemove){
        this.observers = this.observers.filter(observer => 
            observer !== observerToRemove
        )
    },

    notify: function(){
        this.observers.forEach(observer => observer())
    }
}

function Subject1(){
    this.observers = [];
}

Subject1.prototype = {
    subscribe: function(observer,option){
        let {once = false, priority = 0} = option;
        this.observers.push({observer, once , priority});
        this.observers.sort((a, b) => b.priority - a.priority);
    },
    unsubscribe: function(observerToRemove){
        this.observers = this.observers.filter(({observer}) => 
            observer !== observerToRemove
        )
    },
    publish: function(data){
        const current = [...this.observers];
        for(let item of current){
            Promise.resolve().then(() => item.observer(data));
            if(item.once)
                this.unsubscribe(item);
        }
    }
}

const subject1 = new Subject1();
function onlyOnce(data) {
    console.log('只出发一次', data);
}

subject1.subscribe(onlyOnce, {once: true});
subject1.publish('一次');

// 反转列表
const reverseList = (head) => {
    let pre = null;
    let cur = head;
    let next = head;

    while(cur) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
} 

function ListNode(val ,next=null) {
    this.val = val;
    this.next = next;
}

let head = new ListNode(1,new ListNode(2, new ListNode(3)));
// 反转链表
let reversedHead = reverseList(head);

// 打印反转后的链表
let cur = reversedHead;
while(cur){
    console.log(cur.val);
    cur = cur.next;
}

// 防抖:事件在N秒后执行回调，如果在N秒内又被触发，会重新计时。
function debounce(fn, wait) {
    var timer = null;
    return function(...args){
        if(timer)
            clearTimeout(timer);
        timer = setTimeout(() => {
            fn.apply(this, args);
            timer = null;
        }, wait)
    }
}

// 节流: 事件在触发N秒后执行回调，N秒内触发无效
function throttle(fn, delay){
    var timer = null;
    return function(...args){
        if(!timer) {
            timer = setTimeout(() => {
                fn.apply(this, args)
            }, delay);
        }
    }
}

function throttle(fn, delay){
    var prev = Date.now();
    return function(...args){
        var now = Date.now();
        if(now - prev >= delay){
            fn.apply(this, args);
            prev = Date.now();
        }
    }
}

// 归并排序
function merge(left, right) {
    const result = [];
    let i = 0, j = 0;   

    while(i < left.length && j < right.length){
        if(left[i] <= right[j]) {
            result.push(left[i++]);
        }else{
            result.push(right[j++]);
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr) {
    if(arr.length <=1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

const arr = [5, 2, 4, 1, 3];
const sorted = mergeSort(arr);
console.log('归并排序结果：' + sorted);

// 函数柯利化
function curry(fn, ...args){
    return fn.length <= args.length ? fn(...args)
    : curry.bind(this,fn,...args);
}
    // 动态传入参数个数
function dynamicCurry(fn) {
    const args = [];

    function curried(...newArgs) {
        args.push(...newArgs);
        return curried;
    }

    curried.end = function(){
        return fn(...args)
    }

    return curried;
}

function sum(...args) {
    return args.reduce((a,b) => a + b, 0);
  }
  
  const curriedSum = dynamicCurry(sum);
  
  console.log(curriedSum(1)(2,3)(4).end()); 

// 将数组转为树形结构
var menu_list = [{
    id: '1',
    menu_name: '设置',
    menu_url: 'setting',
    parent_id: 0
   }, {
    id: '1-1',
    menu_name: '权限设置',
    menu_url: 'setting.permission',
    parent_id: '1'
   }, {
    id: '1-1-1',
    menu_name: '用户管理列表',
    menu_url: 'setting.permission.user_list',
    parent_id: '1-1'
   }, {
    id: '1-1-2',
    menu_name: '用户管理新增',
    menu_url: 'setting.permission.user_add',
    parent_id: '1-1'
   }, {
    id: '1-1-3',
    menu_name: '角色管理列表',
    menu_url: 'setting.permission.role_list',
    parent_id: '1-1'
   }, {
    id: '1-2',
    menu_name: '菜单设置',
    menu_url: 'setting.menu',
    parent_id: '1'
   }, {
    id: '1-2-1',
    menu_name: '菜单列表',
    menu_url: 'setting.menu.menu_list',
    parent_id: '1-2'
   }, {
    id: '1-2-2',
    menu_name: '菜单添加',
    menu_url: 'setting.menu.menu_add',
    parent_id: '1-2'
   }, {
    id: '2',
    menu_name: '订单',
    menu_url: 'order',
    parent_id: 0
   }, {
    id: '2-1',
    menu_name: '报单审核',
    menu_url: 'order.orderreview',
    parent_id: '2'
   }, {
    id: '2-2',
    menu_name: '退款管理',
    menu_url: 'order.refundmanagement',
    parent_id: '2'
   }
 ]

const buildTree = (arr) => {
    const temp = {};
    const res = {};

    for (let i in arr){
        temp[arr[i].id] = arr[i];
    }
    for(let i in temp){
        if(temp[i].parent_id){
            if(!temp[temp[i].parent_id].children)
                temp[temp[i].parent_id].children = new Object();
            temp[temp[i].parent_id].children[temp[i].id] = temp[i]
        }else {
            res[temp[i].id] = temp[i];
        }
    }
    return res;
}
console.log(JSON.stringify(buildTree(menu_list),null,2))

// 将http header转换为JS对象
/**
 * --- 测试用例 ---
 * 
 * 输入：
 * `Accept-Ranges: bytes 
 * Cache-Control: max-age=6000, public
 * Connection: keep-alive
 * Content-Type: application/javascript`
 * 
 * 输出：
 * {
 *   "Accept-Ranges": "bytes",
 *   "Cache-Control": "max-age=6000, public",
 *   Connection: "keep-alive",
 *   "Content-Type": "application/javascript"
 * }
 */

const solution = (s) => {
    const res = {};
    const arr = s.split('\n');
    arr.forEach(item => {
        let temp = item.split(':');
        res[temp[0]] = temp[1];
    })
    return res;
}

console.log(solution(  `Accept-Ranges: bytes 
Cache-Control: max-age=6000, public
Connection: keep-alive
Content-Type: application/javascript`));

// 快速排序
function quickSort(arr, start, end){
    if(end <= start) return;
    const pivot = arr[start];
    let left = start;
    let right = end;
    while(left < right){
        while(left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right];
        while(left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    quickSort(arr,start, left-1);
    quickSort(arr,left+1, end);
    return arr;
}
const arr1 = [2,4,5,3,1];
console.log(quickSort(arr1, 0, 4));


// 冒泡排序
function bubbleSort(arr) {
    for(let i = 0; i < arr.length - 1; i++){
        for(let j = 0; j < arr.length - 1 - i; j++)
            if(arr[j] > arr[j+1])
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
    return arr;
}
console.log(bubbleSort([1,3,2,4,0,9]));

// 判断是否是回文数
function isPalindrome(x){
    return x.toString().split('').reverse().join('') === x;
}

var a1 = 123454321;
var b1 = 12345;

console.log(isPalindrome(a1));
console.log(isPalindrome(b1));

// 求出一个集合所有的子集
const subSets = (nums) => {
    const res = [];
    function dfs(index, path){
        res.push(path.slice());
        for(let i = index; i < nums.length; i++){
            path.push(nums[i]);
            dfs(i+1, path);
            path.pop()
        }
    }
    dfs([]);
    return res;
}

// 全排列
const permute = (nums) => {
    const res = [];
    const used = {};

    function dfs(path) {
        if(path.length === nums.length){
            res.push(path.slice());
            return;
        }
        for(let num of nums){
            if(used[num]) continue;
            path.push(num);
            used[num] = true;
            dfs(path);
            path.pop();
            used[num] = false;
        }

    }
    dfs([]);
    return res;
}
console.log(permute([1,2,3]));


// 深拷贝
function deepCopy(obj) {
    if(typeof obj !== 'object' && obj === null)
        return obj;
    const result = obj instanceof 'Array' ? [] : {};
    for(const key in obj){
        if(obj.hasOwnProperty(key))
            result[key] = deepCopy(obj[key])
    }
    return obj;
}

// 实现千位分隔符
function numFormat(num) {
    num = num.toString().split(".");
    let arr = num[0].split("").reverse();
    let res = [];
    for(let i = 0; i < arr.length; i++){
        if(i % 3 === 0 && i!== 0)
            res.push(',');
        res.push(arr[i]);
    }
    res.reverse();
    if(num[1])
        res = res.join('').concat('.' + num[1]);
    else 
        res = res.join('');
    return res;
}

// 实现字符串翻转
function reverseString(str) {
    if(str.length <= 1) return str;
    return reverseString(str.slice(1) + str[0]);
}

function reverseString2(str) {
    let res = "";
    for(let i = str.length -1; i >= 0; i--)
        res += str[i]
    return res;
}

// 实现trim方法
function myTrim(str) {
    let reg = /^\s+|\s+$/g
    return str.replace(reg,"");
}

// 实现 setTimeout模拟setInterval
function myInterval(fn, wait) {
    let res = {target: ''};
    function test(){
        fn();
        res.target = setTimeout(test, wait);
    }
    test();
    return res;
}

function myClearInterval(timer) {
    clearTimeout(timer.target);
}

// 手写寄生组合继承

// 手写解析url
/**
 * --- 题目描述 ---
 * 
 * 实现一个函数，可以对 url 中的 query 部分做拆解，返回一个 key: value 形式的 object  
 * 
 * --- 实例 ---
 * 
 * 输入：'http://sample.com/?a=1&e&b=2&c=xx&d#hash' 
 * 输出：{a: 1, b: 2, c: 'xx', d: ''}  
 */

function getQueryObj(url) {
    let queryObj = {};
    urlObj = new URL(url);
    urlObj.search.slice(1, urlObj.search.length)
    .split('&').forEach(item => {
        let arr = item.split('=');
        queryObj[arr[0]] = arr[1] || ''; 
    })
    return queryObj;
}

console.log(getQueryObj(url));
